package com.gump.essay.leetcode;

/**
 * @auther zzc
 * @date 2021/4/1 10:10
 */
public class 颜色分类 {

    //快排
    public void sortColors(int nums[]) {
        quickSort(nums, 0, nums.length - 1);
    }

    private void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int left = start;
        int right = end;
        //随机最左边的数为基准     key
        int key = arr[left];
        while (left < right) {
            //   如果右边的数大于基准数
            while (left < right && arr[right] >= key) {
                right--;
            }
            //交换
            int tmp1 = arr[right];
            arr[right] = key;
            arr[left] = tmp1;

            while (left < right && arr[left] <= key) {
                left++;
            }
            arr[right] = arr[left];
            arr[left] = key;
        }
        quickSort(arr, start, left - 1);
        quickSort(arr, left + 1, end);
    }
}
